The use in diverse applications of bar codes (one-dimensional, such as UPC, Code 39, Code 128; two-dimensional, such as PDF 417, Code 49, Code 16K; etc.), matrix codes (Data Code, Code 1, Vericode, MaxiCode, etc.) and graphic codes (Glyph, etc.) which may be printed or etched on paper, plastic cards and metallic and other items is well known. In addition to such optically machine readable graphics, data is commonly recorded in other machine readable forms, such as optically via invisible ink bar codes or matrix codes and magnetically via magnetic stripes or magnetic ink MICR fonts, on credit cards, checks and identification badges. Similarly, data is recorded electromagnetically via RF tags in a growing variety of forms and applications. Also, in the area of optical character recognition machine readable dataforms take the form of special OCR type fonts and MICR fonts, as well as text including words and numbers formed in the course of ordinary typing and word processing operations. In addition to printing, etching and magnetic recording, other methods of forming or transferring dataforms include engraving, ion doping (for semiconductor wafers), stamping, tattooing (for skin), biochemical binding, etc. For present purposes, all arrangements whereby data is fixed in some form of machine readable copy are termed "dataforms".
In the utilization of dataforms, the data originally encoded is recovered for further use in a variety of ways. For example, a printed bar code may be optically scanned to derive reflectance values which are digitized, stored in buffer memory and subsequently decoded to recover the data encoded in the bar code. Thus, regardless of the particular type of dataform, an image is typically acquired and stored as pixel data for further processing. An image of a bar code or matrix code existing as a graphic image can be acquired by use of a CCD scanner, a laser scanner, a CMOS camera, or other suitable device. For a dataform recorded in a magnetic strip, invisible ink or other medium, magnetic and other techniques available for use with such dataforms are effective for reading the dataform in order to acquire pixel data representative of the elements of the dataform which represent encoded data. The resulting pixel data is stored in an image buffer memory or other medium in bit map or other form which, while representative of a pixel data image, may utilize any appropriate data storage format.
The resolution capabilities, and thereby the cost, of the scanning device or other sensor, as well as the data storage medium, are directly dependent upon the resolution required in the overall decoding process. On a basic level, the resolution characterizing both the pixel data image acquisition and storage must be adequate to permit detection of the position of the smallest image element of interest. For present purposes, the smallest image element of interest is termed a "cell". If, for example, the width of a cell is many times larger than the size of a pixel within the acquired pixel image, it will be appreciated that such cell width will be represented by many pixels and its position will be correspondingly easy to detect. Thus, the resolution, which may be measured in pixels-per-cell, will be high relative to the cell width. Conversely, if a cell dimension is smaller than the size of one pixel in the pixel data image it will not be possible to detect the cell position with accuracy adequate to enable reliable recovery of data encoded in the dataform.
Established sampling theory holds that an image of the present type can be unambiguously represented by samples of the image so long as the image contains no elements or features representative of spatial frequencies greater than one-half the sampling frequency. For present purposes, this translates to a requirement that the width of the cell previously referred to must be no smaller than the dimension represented by two side-by-side pixels in the pixel image. This is another way of expressing the current state of the art standard for bar code decoding, which holds that detecting of a bar code or other dataform requires, as a minimum, at least two pixels-per-cell along one axis. This state of the art minimum requirement is illustrated in FIG. 1a, which shows bar code cells and the pixel size relationship for a few pixels within an overall image. The individual pixels may be in any lateral positioning relationship with the bar code cells and the provision of a least two pixels-per-cell enables determination of the relative cell positions to permit decoding. For the two-dimensional case, as for cells of a matrix code dataform wherein both lateral and vertical positioning of square cells are employed for encoding data, state of the art detecting requires a resolution of at least two pixels per cell along two perpendicular axes, which equates to four pixels-per-cell. This is illustrated in FIG. 1b.
Thus, for a one-dimensional (1-D) laser scanner, CCD scanner or CMOS camera, if a cell width of 0.1 inch is to be detected, for example, the required resolution must be represented by a pixel size no greater than 0.05 inch. For a two-dimensional (2-D) laser scanner, CCD scanner or CMOS camera the same resolution/maximum pixel size requirement applies in each dimension, resulting in the four pixel-per-cell requirement. To achieve the desired decoding resolution, the storage or memory medium must have at least the same resolution capability of storing at least two pixels-per-cell for one axis and four pixels-per-cell for the 2-D case. These standards, together with the overall size and image cell content of a complete dataform to be decoded, determine the overall size, resolution and cost of the sensor unit and storage medium necessary to acquire and store the pixel data image.
As examples of prior patents which describe machine readable dataforms and systems for coding and decoding such dataforms, attention is directed to the following. U.S. Pat. Nos. 5,113,445 and 5,243,655 cover two-dimensional bar code coding and encoding inventions of a present inventor. Earlier U.S. Pat. No. 4,939,354 covers production and reading of two-dimensional data code matrices.
Objects of the present invention are to provide new and improved methods for detecting the position of an image element represented in a pixel data image, and to provide such methods operable with resolutions lower than two pixels-per-cell, thereby achieving subpixel accuracy in cell position detection.